package leetcode.top100;

/**
 * 最长回文子串
 * @date 2020/3/23 17:17
 */
public class Code05_LongestPalindrome {
    //方式1：最所有子串进行判断是否是回文串。o(N³)复杂度。
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return s;
        int max = 1;
        String res = s.substring(0,1);
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(isPalindrome(s,i,j)){
                    if(j - i + 1 > max){
                        max = j - i + 1;
                        res = s.substring(i,j+1);
                    }
                }
            }
        }
        return res;
    }

    private static boolean isPalindrome(String s, int i, int j) {
        while (i < j ){
           if(s.charAt(i) == s.charAt(j)){
               i++;j--;
           }else {
               return false;
           }
        }
        return true;
    }

    //方式2：遍历字符串，遍历过程中对每个位置进行判断，往外扩
    public static String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) return s;

        int start = 0;
        int end = 0;
        String res = s.substring(0,1);
        for (int i = 0; i < s.length(); i++) {
            //对当前位置进行奇偶回文判断
            int len1 = expand(s,i,i);
            int len2 = expand(s,i,i+1);
            int len = Math.max(len1,len2);
            //如果是奇回文，那么对于位置i往前往后都是len/2 = len-1/2。
            //如果是偶回文，那么对于位置i往前是(len-1)/2，往后是len/2
            //所以说往前是len-1/2，往后是len/2
            if(len > end - start +1){
                start = i - (len-1)/2;
                end = i + len/2;
                res = s.substring(start,end+1);
            }
        }
        return res;

    }
    //方式3：对字符串处理，统一处理为奇数个。
    public static String longestPalindrome2(String s) {
        if (s == null || s.length() == 0) return s;
        s = getModify(s);
        int start = 0;
        int end = 0;
        String res = s.substring(0,1);
        for (int i = 0; i < s.length(); i++) {
            //奇回文即可。 1被修饰为#1#，   11被修饰为#1#1#。都是奇回文。
            int len = expand(s,i,i);
            if(len > end - start +1){
                start = i - (len-1)/2;
                end = i + len/2;
                res = s.substring(start,end+1);
            }
        }
        return res.replace("#","");

    }
    private static String getModify(String s) {
        StringBuffer sb = new StringBuffer("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString();
    }

    private  static int expand(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            i--;j++;
        }
        //i+1,j-1;
        i++;
        j--;
        return j-i+1;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("bb"));
        System.out.println(longestPalindrome("a"));
        System.out.println(longestPalindrome("1bb2"));
        System.out.println(longestPalindrome("1bab2"));
    }
}
